An objective of a conventional statistical static timing analysis (SSTA) is to prevent circuit limited yield (CLY) losses by accounting the effects of parametric variability upon switching time distributions of various signals within a digital circuit. A conventional SSTA can be performed at a transistor level or at a gate level, using pre-characterized library elements including those at higher levels of abstraction for complex hierarchical chips.
SSTA algorithms are known to operate by way of a first levelizing the logic structure and breaking any loops in order to create a directed acyclic graph (timing graph). Modern designs can often contain millions of placeable objects, with corresponding timing graphs having millions or tens of millions of nodes. For each node, a corresponding arrival time (AT), a transition rate (slew), and a required arrival time (RAT) are computed for both rising and falling transitions as well an early and late mode analysis. Each value can be represented in general as a distribution, i.e., using a first-order canonical form, wherein timing quantities are represented as functions of underlying sources of variation, as described e.g., in U.S. Pat. No. 7,428,716 to Visweswariah, of common assignee. The arrival time (AT) distribution represents the latest or earliest time at which a signal can transition due to the entire upstream fan-in cone. Similarly, the required arrival time (RAT) distribution represents the latest or earliest time at which a signal must transition due to timing constraints in the entire down stream fan-out cone.
ATs are propagated forward in a levelized manner, starting from a design primary input asserted (i.e., user-specified) arrival times, and ending at either the primary output ports or the intermediate storage elements. In single fan-in cases,AT sink node=AT source node+delay from source to sink.
Whenever multiple signals merge, each fan-in contributes a potential arrival time computed as AT sink (potential)=AT source+delay, making it possible for the maximum (late mode) or minimum (early mode) of all potential arrival times to be statistically computed at the sink node. Typically, an exact delay function for an edge in a timing graph is not known, but instead only the range of possible delay functions can be determined between some minimum delay and a maximum delay. In this case, maximum delay functions are used to compute the late mode arrival times and minimum delay functions used to compute the early mode arrival times.
A timing test (e.g., setup or a hold check) involves a comparison of arrival times in order to determine if the proper ordering relationships between the corresponding signals are satisfied. Such a comparison of AT values produces a quantity known as slack, which when positive in sign indicates that the timing test has been satisfied (and the margin thereof), whereas a negative value indicates a failing test and potential problem.
In an SSTA, when multiple incoming edges merge at a common node, the resulting value is computed by a statistical maximum or minimum operation—generally, the result of which can not be equal to any of the operands. The above applies for all quantities propagated in a block based manner, including arrival times, required times, and slew values. Furthermore, even though an SSTA computes timing values such as slack in a canonical fashion (i.e., as functions of underlying sources of variation), optimization programs typically prefer to deal with scalar quantities, and hence canonicals are sampled by projecting to a worst-case corner in order to create a scalar representation.
Whereas in a deterministic (e.g., single corner) timing, it is guaranteed that the slacks will be continuous along at least one critical path in a design. In an SSTA, due to the aforementioned statistical min/max operations and the projection of canonicals to a worst-case corner, the slack continuity can no longer be guaranteed. In view of the lack of slack continuity, the following situations can arise: it is possible to have an end point (setup or hold test) with failing projected slack, but whose upstream logic all have slack values which are greater (i.e., either less negative, or even positive) as compared to the failing end point.
Further, it is possible to have an intermediate node within the timing graph with a negative slack which feeds end point that all have positive slack values.
To illustrate the above considerations, a small exemplary circuit is shown in FIG. 1 that includes a gate BOX101 having inputs Data1 and Data2 outputted into BOX102 which has as input the output of BOX101, and a second input Data3. BOX104 is connected to a clock attached to an inverter and to a second input provided with an output of BOX2.
FIG. 2 illustrates a corresponding levelized timing graph corresponding to the exemplary circuit of FIG. 1. Each directed edge of the timing graph represents an electrical transition from either a source to sink pin of a wire, or a transition through a circuit element such as an AND gate, Buffer, Latch, and the like. Each node within the timing graph represents either an input or an output pin within the illustrated exemplary circuit. As an example, a simple Buffer is represented by two nodes (one for the input pin and the other for the output pin) connected by a directed edge which represents an electrical transition from the input to the output of the Buffer.
FIG. 3 shows the forward propagation of SSTA late mode arrival times using prior art techniques for statistical timing. In the example, it is assumed that there exist two global statistical sources of variation (“A” and “B) in addition to independently random (“R”). For the purpose of simplicity, as shown in FIG. 3, all the wire segments (shown in dashed lines) are assumed to have a uniform delay value of 5+1ΔB, and all cell segments (shown by solid lines) themselves similarly having a uniform statistical delay value (5+1ΔA). It is assumed that the primary inputs DATA_1, DATA_2, DATA_3 and CLOCK have asserted arrival times, with values as shown in FIG. 3.
FIG. 4 illustrates the backward propagation of SSTA required arrival times, again using well-known prior art methods. For purpose of simplicity, only the data path is shown and it assumed that the required arrival time at BOX104/D is to be equal to the arrival time previously computed at BOX104/C (i.e., assuming a setup test between BOX104/D and BOX104/C, with zero setup timing and cycle adjust).
FIG. 5 shows resulting statistical slack values computed as statistical RAT—statistical AT (assuming a late mode calculation).
FIG. 6 illustrates the resulting 3-sigma projected slack values obtained by projecting each canonical slack to a 3-sigma corner which minimizes the result. For example, at the test location BOX104/D, a canonical slack of 5+0.9ΔR+0.6ΔA+0.5ΔB, is projected to a worst case 3-sigma corner as follows:Projected slack=5+3*(0.9+0.6+0.5)=5−3*(2)=−1
Generally, timing-driven optimization programs work by identifying design elements such as nets and cells with failing slacks and applying transforms to correct timing problems. Such transforms are typically applied in an incremental fashion in such manner that slacks are updated in response to each change (or collection of changes), allowing the timing-driven optimization program evaluate effectiveness of various changes and potentially select from among a range of possible solutions depending on which alternative improves the slack most effectively within given budget constraints such as available power, area, and wiring resources. However, in an SSTA, due to the aforementioned sources of slack discontinuity, timing-driven optimization programs can have difficulties to identify proper locations for applying transforms, and for evaluating the effectiveness thereof.
Still referring to FIG. 6, while a negative 3-sigma projected slack exists at BOX104/D, the negative value of slack only appears with one edge upstream (e.g., on BOX102/Z), whereas all nodes further upstream of BOX102/Z show positive 3-sigma projected slack. Hence, a timing-driven optimization program which uses a negative 3-sigma projected slack as a transform driver can have trouble selecting a location to apply a fix. For example, a transform which looks for negative 3-sigma projected slack at the input of combinatorial boxes in order to select candidate locations for applying transforms would fail to find any such candidates based on 3-sigma projected slack values shown in FIG. 6. Hence, the negative 3-sigma projected slack at BOX104/D can remain in post-optimization (i.e., an optimization program which works in the manner described above would fail to fix such a timing violation identified by SSTA).
Conventional techniques perform timing-driven optimization for SSTA closure using a projection-based form of the statistical min/max operation that ensures that the result is always equal to one of the operands. However, a key drawback of the prior art method is that the proper statistical properties (e.g., the variance) of the result are no longer maintained, and hence the SSTA based on projection-based min/max is considered to be insufficient for timing closure of high-performance digital systems.
In another prior art technique, slacks are periodically transferred between a separate statistical and a deterministic (single-corner) timing environment, followed by an optimization step based on transferred slacks in the deterministic environment. However, a key drawback of the prior-art periodic slack transfer method is that the transferred slack values are not updated incrementally (i.e., statistical and deterministic runs are made separately and do not simultaneously react to design changes), and hence can quickly go stale.
In summary, in a high performance chip design, there is a desire to incrementally re-compute the statistical slack values while maintaining slack continuity properties which are critical for timing-driven optimization programs.
Accordingly, a method and a system capable are provided to maintain slack continuity in incremental statistical timing analysis.